#include <iostream>
#include <map>
#include <vector>
#include <string>

using namespace std;


int** knapsackD (int W, int n, vector<int> &weight, vector<int> &value, int** &f);
void printSackD(int** &f, int count, int W);
void SortLists(vector<int> &w, vector<int> &v, int n);
int knapsackG (int W, int n, vector<int> &weight, vector<int> &value);

int RUNNINGTIME = 0;

int main()
{
	vector<int> weight;
	vector<int> value;
	int W;
	int x;
	int v;
	int count = 0;

	cout << "Welcome to the knapsack problem!";
	
	cout << "\n\nPlease enter in the max holding weight of the knapsack: ";
	cin >> W;
	W += 1;

	cout << "\nI will now need to populate the item set to steal from enter a -1 \nin for the weight to stop. \nI can print out matrix if the number of items is below 8.";
	do
	{
		cout << "\n\nPlease enter in the weight of item" << count+1 << " in your set: ";
		cin >> x;
		if (x != -1)
		{
			weight.push_back(x);
			cout << "\nPlease enter int the value of item" << count+1 << ": ";
		 	cin >> v;
			value.push_back(v);
			count ++;
		}
	}while (x != -1);
	cout << "\n\nAccording to you enteries you have a knapsack that can hold a weight of " << W << ".\nAnd there are " << count << " Items to choose from.";
	cout << "\nNow calculating what would be in the knapsack using the dynamic approach.";

	int** KnapsackMatrix = new int*[count+1];
	int i;

	for (i = 0; i <= count; i++)
	{
		KnapsackMatrix[i] = new int[W +1];  // allocate memory for my matrix
	}

	for (i = 0; i <= W; i++)
	{
		KnapsackMatrix[0][i] = 0;
	}

	for (i = 0; i <= count; i++)
	{
		KnapsackMatrix[i][0] = 0;
	}

	KnapsackMatrix = knapsackD(W, count, weight, value, KnapsackMatrix);
	printSackD(KnapsackMatrix, count, W);

	cout << "\nNow calculating what would be in the knapsack using the greedy approach.";
	SortLists(weight, value, count);
	cout << "\n\nThe max value for this napsack and set would be: " << knapsackG(W, count, weight, value);;
	cout << "\n\nAnd the running time for Knapsack Greedy is: " << RUNNINGTIME;
	system("Pause");
	return 0;
}
int knapsackG (int W, int n, vector<int> &weight, vector<int> &value)
{
	RUNNINGTIME = 0;
	int totalWght = 0;
	int totalVal = 0;
	for (int i = 0; i < n; i++)
	{
		RUNNINGTIME ++;
		if (totalWght + weight[i] < W)
		{
			cout << "\nTaking " << weight[i] << " for " << value[i];
			totalWght += weight[i];
			totalVal += value[i];
		}
	}
	return totalVal;
}

void printSackD(int** &f, int count, int W)
{
	if (count > 8)
	{
		cout << "\nThere are too many items to display Matrix.";
		cout << "\nThe max value for this napsack and set would be: ";
		cout << f[count][W];
		cout << "\nAnd the running time for Knapsack Dynamic Approach is: ";
		cout << RUNNINGTIME;
		return;
	}
	int i = 0;
	int x = 0;
	cout << endl;
	cout << "item:";
	for (i = 0; i <= count; i++)
		cout << "\t" << i + 1;
	for (i = 0; i + 1 <= W; i++)
	{
		cout << "\n" << i << ": ";
		for (x = 0; x <= count; x++)
		{
			cout << "\t" << f[x][i];
		}
	}
	cout << "\nThe max value for this napsack and set would be: ";
	cout << f[count][W];
	cout << "\nAnd the running time for Knapsack Dynamic Approach is: ";
	cout << RUNNINGTIME;
}

int** knapsackD (int W, int n, vector<int> &weight, vector<int> &value, int** &f)
{
	int w, i;
	for (i = 1; i <= n; i++)
	{
		for (w = 1; w <= W; w++)
		{
			f[i][w] = f[i-1][w];
			if (w - weight[i-1] >= 0)
			{
				int tmp1 = f[i-1][w - weight[i-1]] + value[i-1];
				if (tmp1 > f[i-1][w])
				{
					f[i][w] = tmp1;
					RUNNINGTIME ++;
				}
			}
		}
	}
	return f;
}

void SortLists(vector<int> &w, vector<int> &v, int n) 
{
	int *wvArray = new int[n + 1];
	int *wArray = new int[n + 1];
	int *vArray = new int[n + 1];
	for (int i = 0; i < n; i ++)
	{
		wArray[i] = w[i];
		vArray[i] = v[i];
		wvArray[i] = (v[i]/w[i]);
	}
	for (int p=1; p < n; p++) 
	{
		for (int i=0; i < n-p; i++)
		{
			if (wvArray[i] > wvArray[i+1]) 
			{
				int tmp = wvArray[i]; 
				wvArray[i] = wvArray[i+1]; 
				wvArray[i+1] = tmp;
				tmp = wArray[i];
				wArray[i] = wArray[i+1];
				wArray[i+1] = tmp;
				tmp = vArray[i];
				vArray[i] = vArray[i+1];
				vArray[i+1] = tmp;
			}
		}
	}
	w.clear();
	v.clear();
	for (int i = 0; i < n; i ++)
	{
		w.push_back(wArray[i]);
		v.push_back(vArray[i]);
	}
}